package review;

import java.util.HashMap;
import java.util.HashSet;

public class LeetCode_day3_review {

	public static String longestPalindromicSubstring(String str){
		if(str == null || str.length() <= 1) return str;
		char[] s = str.toCharArray();
		int maxLen = 1, left = 0;

		for(int i = 1 ; i < s.length-1 ; i++){
			int l = i-1, r = i+1;
			while(l >= 0 && r < s.length && s[l] == s[r]){
				int len = r-l+1;
				if(len > maxLen){
					maxLen = len; left = l;
				}
				l--;
				r++;
			}
			
			if(s[i] == s[i+1]){
				l = i-1; r = i+2;//wrong point
				while(l >= 0 && r < s.length && s[l] == s[r]){
					int len = r-l+1;
					if(len > maxLen){
						maxLen = len; left = l;
					}
					l--;
					r++;
				}	
			}
		}
		return str.substring(left, left+maxLen);
	}
	
	public static String longestPalindromicSubstring1(String str){
		if(str == null || str.length() <= 1) return str;
		char[] s = str.toCharArray();
		int maxLen = 1, left = 0;
		boolean[][] t = new boolean[s.length][s.length];
		
		for(int i = 0 ; i < s.length ; i++) t[i][i] = true;
		for(int i = 0 ; i < s.length-1 ; i++)
			if(s[i] == s[i+1]) t[i][i+1] = true;
		
		for(int len = 3 ; len < s.length ; len++){//for every possible lens
			for(int l = 0 ; l < s.length-len+1 ; l++){//for every possible left//wroing point
				int r = l+len-1;//get the possible r
				if(t[l+1][r-1] == true){
					t[l][r] = true;
					maxLen = len;
					left = l;
				}
			}
		}
		return str.substring(left, left+maxLen);
	}
	
	public static String longestUnrepeatedSubstring(String str){
		if(str == null || str.length() <= 1) return str;
		char[] s = str.toCharArray();
		int maxLen = 1 , start = 0;
		HashMap<Character, Integer> set = new HashMap<Character ,Integer>();
		
		for(int i = 0 ; i < s.length-maxLen+1 ; i++){//start position
			set.clear(); boolean rFlag = false;
			int nextStart = i;
			for(int k = i ; k < i+maxLen ; k++){
				if(set.containsKey(s[k])){
					rFlag = true;
					nextStart = k-1;
					break;
				}else set.put(s[k], k);
			}
			if(rFlag) i = nextStart;
			
			for(int j = i+maxLen ; j < s.length ; j++){
				if(set.containsKey(s[j])){
					int len = j-i;
					if(len > maxLen){
						maxLen = len;
						start = i;
					}
					nextStart = set.get(s[j]) - 1;
					rFlag = true;
					break;
				}else set.put(s[j], j);
			}
			
			if(!rFlag){
				int len = s.length-i;
				if(len > maxLen){
					maxLen = len;
					start = i;
				}
				break;
			}
		}
		return str.substring(start, start+maxLen);
	}

	//TODO
	public static boolean regularExpressionMatching(String str, String expression){
		if(str == null || expression == null) return false;
		char[] s = str.toCharArray(), e = expression.toCharArray();
		int si=0, ei=0;
		
		while(si < s.length){
			if(ei >= e.length) return false;// no states available
			//if accept
			if(e[ei] == s[si] || e[ei] == '.'){
				//check whether it is the end of the input
				if(si+1 > s.length){
					if(ei == e.length - 1) return true;
					else{
						for(int i = e.length-1 ; i >= ei+1 ; i-=2){
							if(e[i] != '*') return false;
						}
						return true;//if the remaining expression has the mode of 'a*b*', then accept
					}
				}//if not the end of the input, determine whether stay
				else{
					if(ei + 1 >= e.length) {//no next states, no stay
						si++; ei++;
					}else{
						if(e[ei+1] == '*'){
							if(si + 1 < s.length){
								
							}
						}
					}
				}
			}else{
				
			}
		}
		
		
		return true;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(longestPalindromicSubstring1("cabba"));
		System.out.println(longestUnrepeatedSubstring("abcsdabcews"));
	}

}
